package cn.cxq.learning.sort;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * 牛客题霸-全部题目
 * 排序
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：110043
 * 本题知识点： 排序
 *  算法知识视频讲解
 * 题目描述
 * 给定一个数组，请你编写一个函数，返回该数组排序后的形式。
 * 示例1
 * 输入
 * 复制
 * [5,2,3,1,4]
 * 返回值
 * 复制
 * [1,2,3,4,5]
 * 示例2
 * 输入
 * 复制
 * [5,1,6,2,5]
 * 返回值
 * 复制
 * [1,2,5,5,6]
 */
public class MySort {

    @Test
    public void test() {
        int[] arr = {12, 34, 2, 0, 345, 3, 2423, 45, 99, 4, 5, 356, 6, 2, 232};
        MySort(arr);

        System.out.println(Arrays.toString(arr));
    }

    public int[] MySort(int[] arr) {
        // write code here
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);

        return arr;
    }

    private void mergeSort(int[] arr, int left, int right, int[] temp) {

        int mid = (left + right) / 2;

        if (left < right) {
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int index = left;

        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[index++] = arr[i++];
            } else {
                temp[index++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[index++] = arr[i++];
        }

        while (j <= right) {

            temp[index++] = arr[j++];
        }

        while (left <= right) {
            arr[left] = temp[left++];
        }
    }
}